#pragma GCC optimize(3, "Ofast", "inline")
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
#include <iostream>
#include <sys/mman.h>
#include <unistd.h>
#include <fcntl.h>
#include <stdio.h>
#include <sys/time.h>

#define THREAD_COUNT 4
#define fi first
#define se second
#define pii pair<int, int>
using namespace std;

using namespace std;
const int N = 3e6 + 5;
const int M = 6e5 + 5;
const char numchar[10] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
int m, n;
int val[M];
bool can[M];
pii p[N],q[N];
string numstring[M];
string ansstring;
unordered_map<int, int> mp;

bool cmp(pii a, pii b) {
    return a.se > b.se;
}

bool cmp1(pii a, pii b) {
    return a.se < b.se;
}

struct G_Edge {
    struct Edge {
        int v, next;
    } edge[M];

    int head[M], cnt;

    void init(int n) {
        if (cnt != 0) n = cnt + 10;
        cnt = 0;
        memset(head, -1, sizeof(int) * n);
    }

    void add(int u, int v) {
        edge[cnt] = {v, head[u]};
        head[u] = cnt++;
    }
} G1, G2, G3;

struct find_huan {
    bool flag[M];
    int len[N], cur[15];
    int **ans;
    int is[M], num, f[M], dis[M];
    int que[M], rt;
    int _head, _tail;

    struct info {
        struct Edge {
            int a[2];
            int next;
        } edge[M];

        int head[M], cnt = 0;
        int clr[M], num = 0;

        void init() {
            for(int i = 1; i <= num; i+=4) {
                head[clr[i]] = -1;
                head[clr[i+1]] = -1;
                head[clr[i+2]] = -1;
                head[clr[i+3]] = -1;
            }
            cnt = 0;
            num = 0;
        }

        void add(int u, int a[]) {
            edge[cnt].a[0] = a[3];
            edge[cnt].a[1] = a[2];
            edge[cnt].next = head[u];
            head[u] = cnt++;
        }
    } q;


    inline void add_ans(int now_len) {

        ans[num][1] = cur[1];
        ans[num][2] = cur[2];
        ans[num][3] = cur[3];
        if (now_len == 3) return;
        ans[num][4] = cur[4];
        if (now_len == 4) return;
        ans[num][5] = cur[5];
        if (now_len == 5) return;
        ans[num][6] = cur[6];
        if (now_len == 6) return;
        ans[num][7] = cur[7];
    }

    void add_ans_2(int u, int now_len) {

        for (int i = q.head[u]; ~i; i = q.edge[i].next) {
            auto a = q.edge[i].a;
            if (flag[a[0]] || flag[a[1]]) continue;

            len[++num] = now_len + 2;
            add_ans(now_len);
            ans[num][now_len+1] = a[0];
            ans[num][now_len+2] = a[1];
        }
    }

    void dfs(int u, int step) {
        if (u < rt || flag[u]) return;

        cur[step] = u;

        // 3 4 5
        if (step >= 3  && f[u] == rt) {
            len[++num] = step;
            add_ans(step);
        }
        flag[u] = true;
        // 6 7
        if(step >= 4 && is[u] == rt) add_ans_2(u, step);
        if(step == 5) {
            flag[u] = false;
            return;
        }
        for (int i = G1.head[u]; ~i; i = G1.edge[i].next) {
            dfs(G1.edge[i].v, step + 1);
        }
        flag[u] = false;
    }

    void dfs_ni(int u, int step) {
        if (u < rt || flag[u]) return;
        cur[step] = u;
        if (step == 4) {
            q.add(u, cur);
            if(is[u] != rt) {
                is[u] = rt;
                q.clr[++q.num] = u;
            }
            return;
        }
        flag[u] = true;
        for (int i = G3.head[u]; ~i; i = G3.edge[i].next) {
            dfs_ni(G3.edge[i].v, step + 1);
        }
        flag[u] = false;
    }


    void start(int l, int r) {
        if (l > r) return;

        bool ok = true;
        for (int i = l; i <= r; i++) {
            if(!can[i]) continue;
            ok = false;
            rt = i;
            _head = _tail = 0;
            for (int j = G2.head[i]; ~j; j = G2.edge[j].next) {
                f[G2.edge[j].v] = i;
                ok = true;
            }

            if (ok) {
                q.init();
                dfs_ni(i, 1);
                dfs(i, 1);
            }
        }
    }
} T[THREAD_COUNT];


struct tag_mmap {
    // 要读取源文件的起始内存位置
    void *r_mem;
    // 要写入目标文件的起始内存位置
    void *w_mem;
    // 要复制的大小
    unsigned long long m_size;
};

//多线程拷贝
void threadfunc(tag_mmap arg) {
    char *r = (char *) arg.r_mem;
    char *w = (char *) arg.w_mem;
    memcpy(w, r, arg.m_size);
}

inline void pr(int d[], int now_len) {
    ansstring += numstring[d[1]];
    ansstring += ',';
    ansstring += numstring[d[2]];
    ansstring += ',';
    if (now_len == 3) {
        ansstring += numstring[d[3]];
        ansstring += '\n';
        return;
    }
    ansstring += numstring[d[3]];
    ansstring += ',';
    if (now_len == 4) {
        ansstring += numstring[d[4]];
        ansstring += '\n';
        return;
    }
    ansstring += numstring[d[4]];
    ansstring += ',';
    if (now_len == 5) {
        ansstring += numstring[d[5]];
        ansstring += '\n';
        return;
    }
    ansstring += numstring[d[5]];
    ansstring += ',';
    if (now_len == 6) {
        ansstring += numstring[d[6]];
        ansstring += '\n';
        return;
    }
    ansstring += numstring[d[6]];
    ansstring += ',';
    ansstring += numstring[d[7]];
    ansstring += '\n';
}


inline void mmap_readdata(char *filename) {
    char *data = NULL;
    int fd = open(filename, O_RDONLY);
    long size = lseek(fd, 0, SEEK_END);
    data = (char *) mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);
    int u, v, cost;
    int tmp = 0;
    int i = 0, j = 0;
    while (data[i] != '\0') {
        if (data[i] >= '0' && data[i] <= '9') {
            tmp *= 10;
            tmp += data[i] - '0';
        } else if (data[i] == ',') {
            if (j == 0) {
                u = tmp;
                j++;
            } else if (j == 1) {
                v = tmp;
                p[++m] = {u, v};
                q[m] = {v, u};
                val[++n] = u;
                val[++n] = v;
            }
            tmp = 0;
        } else {
            //cost = tmp;
            //printf("%d\n", w);
            j = 0;
            tmp = 0;
        }
        ++i;
    }
}

inline string numtostring(int x) {
    string tmp = "";
    if (x == 0) {
        return "0";
    }
    while (x != 0) {
        tmp += numchar[x % 10];
        x /= 10;
    }
    if (tmp.size() == 1)return tmp;
    reverse(tmp.begin(), tmp.end());
    return tmp;
}

void find_thread(int tid, int s, int t) {
    T[tid].start(s, t);
}

void prtime(char *pos, timeval &time) {
    printf("%s=",pos);
    struct timeval now;
    gettimeofday(&now, NULL);
    printf("%dms\n",int((now.tv_sec * 1000 + now.tv_usec / 1000) - (time.tv_sec * 1000 + time.tv_usec / 1000)));
    time = now;
}

int main() {
    timeval start;
    gettimeofday(&start, NULL);
    struct timeval time;
    gettimeofday(&time, NULL);
    char *readfile = "./data/2861665/test_data.txt";
    char *outfile = "./z1.out";
//    char *readfile = "/data/test_data.txt";
//    char *outfile = "/projects/student/output.txt";
    mmap_readdata(readfile);
    prtime("读数据时间 ", time);
    // 离散化
    G1.cnt = G2.cnt = G3.cnt = 0;
    sort(val + 1, val + n + 1);
    prtime("sort节点时间 ", time);
    n = unique(val + 1, val + n + 1) - val - 1;
    for (int i = 1; i <= n; i++) {
        mp[val[i]] = i;
    }
    prtime("离散化时间 ", time);
    for (int i = 1; i <= n; i++) {
        numstring[i] = numtostring(val[i]);
    }
    prtime("转字符串时间 ", time);
    sort(p + 1, p + m + 1, cmp);
    sort(q + 1, q + m + 1, cmp1);
    prtime("sort p时间 ", time);
    G1.init(n + 5);
    G2.init(n + 5);
    G3.init(n + 5);

   for(int i=0;i<THREAD_COUNT;++i)memset(T[i].q.head,-1, sizeof(T[i].q.head));

    for (int i = 1; i <= m; i++) {
        int u = mp[p[i].fi];
        int v = mp[p[i].se];
        if (u < v) can[u] = true;
        G1.add(u, v);
        u = mp[q[i].fi];
        v = mp[q[i].se];
        G3.add(u, v);
        if (u < v)
            G2.add(u, v);
    }

    prtime("重新建图时间", time);
    //开启多线程找环
    if (n < 8) {
        T[0].start(1, n);
        ansstring += numtostring(T[0].num);
        ansstring += '\n';
        for (int j = 3; j <= 7; j++) {
            for (int i = 1; i <= T[0].num; i += 4) {
                if (T[0].len[i] == j) pr(T[0].ans[i], j);
                if (T[0].len[i + 1] == j) pr(T[0].ans[i + 1], j);
                if (T[0].len[i + 2] == j) pr(T[0].ans[i + 2], j);
                if (T[0].len[i + 3] == j) pr(T[0].ans[i + 3], j);
            }
        }
    } else {
        std::thread threads_find[THREAD_COUNT];
        const int nCount = n / THREAD_COUNT;

        for (int i = 0; i < THREAD_COUNT; i++) {
            int s, t;
            if (i < THREAD_COUNT - 1) {
                s = i * nCount + 1;
                t = (i + 1) * nCount;
            } else {
                s = i * nCount + 1;
                t = n;
            }
            threads_find[i] = std::thread(find_thread, i, s, t);
        }
        for (int i = 0; i < THREAD_COUNT; ++i) {
            threads_find[i].join();
        }
        prtime("找环时间 ", time);
        //统计结果
        int result = 0;
        for (int i = 0; i < THREAD_COUNT; ++i)result += T[i].num;
        ansstring += numtostring(result);
        ansstring += '\n';
        for (int j = 3; j <= 7; j++) {
            for (int k = 0; k < THREAD_COUNT; ++k)
                for (int i = 1; i <= T[k].num; i += 4) {
                    if (T[k].len[i] == j) pr(T[k].ans[i], j);
                    if (T[k].len[i + 1] == j) pr(T[k].ans[i + 1], j);
                    if (T[k].len[i + 2] == j) pr(T[k].ans[i + 2], j);
                    if (T[k].len[i + 3] == j) pr(T[k].ans[i + 3], j);
                }
        }
    }
    prtime("拼接答案时间 ", time);

    //多线程mmap输出
    int wfd;
    wfd = open(outfile, O_RDWR | O_CREAT | O_TRUNC, 0666);
    lseek(wfd, ansstring.length() - 1, SEEK_SET);
    write(wfd, "\0", 1);
//    void *w_mem = mmap(NULL, ansstring.length(), PROT_WRITE, MAP_SHARED, wfd, 0);
//    memcpy(w_mem, ansstring.c_str(), ansstring.length());
//    munmap(w_mem, ansstring.length());

    const long long nCount = ansstring.length() / THREAD_COUNT;
    const long long nPages = nCount - (nCount % 4096);
    const long long nSplit = ansstring.length() - THREAD_COUNT * nPages;
    if (nCount < 4096) {
        void *w_mem = mmap(NULL, ansstring.length(), PROT_WRITE, MAP_SHARED, wfd, 0);
        memcpy(w_mem, ansstring.c_str(), ansstring.length());
        munmap(w_mem, ansstring.length());
    } else {
        struct tag_mmap mm[THREAD_COUNT];
        std::thread threads[THREAD_COUNT];
        for (int i = 0; i < THREAD_COUNT; ++i) {
            if (i < THREAD_COUNT-1) {
                mm[i].r_mem = (void *) (ansstring.c_str() + i * nPages);
                mm[i].w_mem = mmap(NULL, nPages, PROT_WRITE, MAP_SHARED, wfd, i * nPages);
                mm[i].m_size = nPages;
                threads[i] = std::thread(threadfunc, mm[i]);
            } else {
                mm[i].r_mem = (void *) (ansstring.c_str() + i * nPages);
                mm[i].w_mem = mmap(NULL, nPages + nSplit, PROT_WRITE, MAP_SHARED, wfd, i * nPages);
                mm[i].m_size = nPages + nSplit;
                threads[i] = std::thread(threadfunc, mm[i]);
            }
        }
        for (int join = 0; join < THREAD_COUNT; join++) {
            threads[join].join();
        }
        for (int un = 0; un < THREAD_COUNT; un++) {
            munmap(mm[un].r_mem, mm[un].m_size);
            munmap(mm[un].w_mem, mm[un].m_size);
        }
    }
    prtime("输出答案时间 ", time);
    prtime("总时间 ", start);
    return 0;
}

